#include "kMST_ILP.h"

kMST_ILP::kMST_ILP( Instance& _instance, string _model_type, int _k ) :
	instance( _instance ), model_type( _model_type ), k( _k )
{
	n = instance.n_nodes;
	m = instance.n_edges;
	if( k == 0 ) k = n;
}

void kMST_ILP::solve()
{
	// initialize CPLEX solver
	initCPLEX();

	// add common constraints
	modelCommon();

	// ++++++++++++++++++++++++++++++++++++++++++
	// TODO solve model
	// ++++++++++++++++++++++++++++++++++++++++++

	try {
		// build model
		cplex = IloCplex( model );
		//cplex.exportModel( "model.lp" );

		// set parameters
		epInt = cplex.getParam( IloCplex::EpInt );
		epOpt = cplex.getParam( IloCplex::EpOpt );
		setCPLEXParameters();

		// set cut- and lazy-constraint-callback for
		// cycle-elimination cuts ("cec") or directed connection cuts ("dcc")
		CutCallback* usercb = new CutCallback( env, model_type, epOpt, instance, x, z, e, k );
		CutCallback* lazycb = new CutCallback( env, model_type, epOpt, instance, x, z, e, k );
		cplex.use( (UserCutI*) usercb );
		cplex.use( (LazyConsI*) lazycb );

		// solve model
		cout << "Calling CPLEX solve ...\n";
		cplex.solve();
		cout << "CPLEX finished.\n\n";
		cout << "CPLEX status: " << cplex.getStatus() << "\n";
		cout << "Instance: "<<instance.name<<" k=" <<k<< "\n";
		cout << "Added violated constraints: " << CutCallback::numberOfAddedViolatedInequalities<< "\n";
		cout << "Branch-and-Bound nodes: " << cplex.getNnodes() << "\n";
		cout << "Objective value: " << cplex.getObjValue() << "\n";
		cout << "CPU time: " << Tools::CPUtime() << "\n\n";
		

		//finalOutput();

	}
	catch( IloException& e ) {
		cerr << "kMST_ILP: exception " << e.getMessage();
		exit( -1 );
	}
	catch( ... ) {
		cerr << "kMST_ILP: unknown exception.\n";
		exit( -1 );
	}
}

// ----- private methods -----------------------------------------------

void kMST_ILP::finalOutput()
{
	int counter=0;
	for (Instance::Edge edge : instance.edges)
	{
		unsigned vi[2] = {edge.v1, edge.v2};
		for (unsigned i=0;i<2;i++)
		{
			unsigned v1 = vi[0^i];
			unsigned v2 = vi[1^i];

			if (v2 != 0)
			{
				const char* name = e[v1*n+v2]->getName();
				IloNum val = cplex.getValue(*e[v1*n+v2]);
				int intVal = (int)floor(val+0.5);
				if (intVal==1)
				{
					cout << name << ": " << val << endl;
					counter++;
				}
			}
		}
	}
	cout << "Num edges: " << counter << endl;
}

void kMST_ILP::initCPLEX()
{
	cout << "initialize CPLEX ... ";
	try {
		env = IloEnv();
		model = IloModel( env );
		values = IloNumArray( env );
	}
	catch( IloException& e ) {
		cerr << "kMST_ILP: exception " << e.getMessage();
	}
	catch( ... ) {
		cerr << "kMST_ILP: unknown exception.\n";
	}
	cout << "done.\n";
}

void kMST_ILP::setCPLEXParameters()
{
	// print every line of node-log and give more details
	cplex.setParam( IloCplex::MIPInterval, 100 );
	cplex.setParam( IloCplex::MIPDisplay, 2 );
	// deactivate CPLEX general-purpose cuts
	//cplex.setParam( IloCplex::EachCutLim, 0 );
	//cplex.setParam( IloCplex::FracCuts, -1 );
	// only use a single thread
	cplex.setParam( IloCplex::Threads, 1 );


}

void kMST_ILP::modelCommon()
{
	// ++++++++++++++++++++++++++++++++++++++++++++++++
	// TODO add common constraints for both cut models
	// ++++++++++++++++++++++++++++++++++++++++++++++++

	//x = IloBoolVarArray(env, n*n);
	// e[v1*n+v2] is edge variable from v1 to v2
	e = new IloBoolVar*[n*n];
	z = IloBoolVarArray(env,n);

	// generate two directed edge variables for each edge in the graph. For virtual edges 0v only one variable 0->v is created.
	vector<IloBoolVar*> allEdgeVariables;
	vector<int> allEdgeWeights;
	for (Instance::Edge edge : instance.edges)
	{
		unsigned vi[2] = {edge.v1, edge.v2};
		for (unsigned i=0;i<2;i++)
		{
			unsigned v1 = vi[0^i];
			unsigned v2 = vi[1^i];

			if (v2 != 0)
			{
				ostringstream oss;
				oss << "Edge " << v1 << "->" << v2;
				IloBoolVar* edgeVar = new IloBoolVar(env, oss.str().c_str());
				allEdgeVariables.push_back(edgeVar);
				allEdgeWeights.push_back(edge.weight);
				e[v1*n+v2] = edgeVar;
				//cout << "Generated " << oss.str() << endl;
			}
		}
	}

	// exactly one edge outgoing from 0
	IloExpr oneEdgeFrom0(env);
	for (unsigned i=1; i<n; i++)
	{
		oneEdgeFrom0 += *e[0*n+i];
	}
	model.add(oneEdgeFrom0 == 1);
	oneEdgeFrom0.end();

	// at most one incoming edge at each vertex
	// a vertex can only have outgoing edges if there is an incoming edge
	for (unsigned i=1; i<n; i++)
	{
		/*Debug
		if (i==57)
			cout << i;
		*/

		IloExpr sumIncoming(env);
		IloExpr sumOutgoing(env);
		for (unsigned edgeIndex : instance.incidentEdges[i])
		{
			Instance::Edge edge = instance.edges[edgeIndex];
			unsigned neighbor = (edge.v1 == i) ? edge.v2 : edge.v1;

			sumIncoming += *e[neighbor*n+i];
			if (neighbor != 0)
			{
				sumOutgoing += *e[i*n+neighbor];
			}
		}
		model.add(sumIncoming <= 1);
		model.add(sumOutgoing <= (k-1)*sumIncoming);
		sumIncoming.end();
		sumOutgoing.end();
	}

	// select k edges in total
	IloExpr sumEdges(env);
	for (IloBoolVar* var : allEdgeVariables)
	{
		sumEdges += *var;
	}
	model.add(sumEdges == k);
	sumEdges.end();

	// no length-2 cycles
	for (Instance::Edge edge : instance.edges)
	{
		if (edge.v1 != 0 && edge.v2 != 0)
		{
			model.add(*e[edge.v1*n+edge.v2] + *e[edge.v2*n+edge.v1] <= z[edge.v1]);
			model.add(*e[edge.v1*n+edge.v2] + *e[edge.v2*n+edge.v1] <= z[edge.v2]);
		}
	}

	// select all nodes with incoming edge
	model.add(z);
	for (unsigned i=1;i<n;i++)
	{
		IloExpr sumIncoming(env);
		for (unsigned edgeIndex : instance.incidentEdges[i])
		{
			Instance::Edge edge = instance.edges[edgeIndex];
			unsigned neighbor = (edge.v1 == i) ? edge.v2 : edge.v1;

			sumIncoming += *e[neighbor*n+i];
		}
		model.add(z[i] == sumIncoming);
		sumIncoming.end();
	}
	model.add(z[0]== 1);

	// restrict symmetry
	for (unsigned j=0;j<n;j++)
	{
		for (unsigned i=1;i<j;i++)
		{
			model.add(*e[0*n+j] <=  1-z[i]);
		}
	}

	// objective function
	IloExpr objective(env);
	for (unsigned i=0;i<allEdgeVariables.size();i++)
	{
		objective += *allEdgeVariables[i] * allEdgeWeights[i];
	}

	model.add(IloMinimize(env,objective));
}

kMST_ILP::~kMST_ILP()
{
	// free CPLEX resources
	cplex.end();
	model.end();
	env.end();
}
